package leetcode;

import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;
import java.util.PriorityQueue;

public class KthSmallestElement {

	public static void main(String[] args) {
		KthSmallestElement test = new KthSmallestElement();
//		int[][] matrix = {{1, 5, 9}, {10, 11, 13}, {12, 14, 15}};
//		test.kthSmallest(matrix, 8);
		
		int[] nums1 = {1, 2, 4, 5, 6};
		int[] nums2 = {3, 5, 7, 9};
		test.kSmallestPairs(nums1, nums2, 4);
		System.out.println("----");
		test.kSmallestPairs_2(nums1, nums2, 4);
		PriorityQueue<TuplePair> heap = new PriorityQueue<>();
		for (int i = 0; i < 2; i++) {
			for (int j = 0; j < nums2.length; j++) {
				heap.offer(new TuplePair(i, j, nums1[i], nums2[j]));
				System.out.println(heap);
			}
		}
		
		PriorityQueue<Tuple> heap2 = new PriorityQueue<>();
		for (int i = 0; i < 2; i++) {
			for (int j = 0; j < nums2.length; j++) {
				heap2.offer(new Tuple(i, j, nums1[i] + nums2[j]));
				System.out.println(heap2);
			}
		}
		Iterator<Tuple> iterator = heap2.iterator();
		for (int i = 0; iterator.hasNext(); i++) {
			Tuple temp = heap2.poll();
			System.out.println(temp.val);
			System.out.println(heap2);
		}
	}
	public int kthSmallest(int[][] matrix, int k) {
		if(matrix == null){
			throw new IllegalArgumentException("the array can't be null");
		}
		int n = matrix.length;
		//use priorityQueue create a heap
		PriorityQueue<Tuple> heap = new PriorityQueue<>();
		//initial the heap
		for (int j = 0; j < matrix.length; j++) {
			heap.offer(new Tuple(0, j, matrix[0][j]));
		}
		Iterator<Tuple> iterator = heap.iterator();
		while(iterator.hasNext()){
			System.out.print(iterator.next().val + " ");
		}
		for(int i = 1; i < k; i++){
			//寻找最小的堆中的元素，并从对中移除
			Tuple tuple = heap.poll();
			if(tuple.i == n - 1){
				continue;
			}
			//每次加入下一行中的同列的元素
			heap.offer(new Tuple(tuple.i + 1, tuple.j, matrix[tuple.i + 1][tuple.j]));
		}
		return heap.poll().val;
	}
	
	
	//leetcode373 : find k pairs with smallest sums
    //
	public List<int[]> kSmallestPairs(int[] nums1, int[] nums2, int k) {
		PriorityQueue<TuplePair> heap = new PriorityQueue<>();
		for (int i = 0; i < nums1.length; i++) {
			heap.offer(new TuplePair(i, 0, nums1[i], nums2[0]));
		}
		List<int[]> list = new ArrayList<int[]>();
		int min = Math.min(k, nums1.length * nums2.length);
		for (int i = 0; i < min; i++) {
			TuplePair tuplePair = heap.poll();
			list.add(new int[]{tuplePair.firstPair, tuplePair.secondPair});
			if(tuplePair.j == nums2.length - 1){
				continue;
			}
			heap.offer(new TuplePair(tuplePair.i, tuplePair.j + 1, nums1[tuplePair.i], 
					nums2[tuplePair.j + 1]));
		}
		
		System.out.println(heap);
		
		int length = list.size();
		for (int i = 0; i < length; i++) {
			int[] array = list.get(i);
			for (int j = 0; j < array.length; j++) {
				System.out.print(array[j] + " ");
			}
			System.out.println();
		}
		return list;
    }
	
	public List<int[]> kSmallestPairs_2(int[] nums1, int[] nums2, int k) {
		List<int[]> list = new ArrayList<int[]>();
		if(nums1 == null || nums1.length <= 0 || nums2 == null || nums2.length == 0){
			return list;
		}
		PriorityQueue<Tuple> heap = new PriorityQueue<>();
		for (int i = 0; i < nums1.length; i++) {
			heap.offer(new Tuple(i, 0, nums1[i] + nums2[0]));
		}
		int min = Math.min(k, nums1.length * nums2.length);
		for (int i = 0; i < min; i++) {
			Tuple tuple = heap.poll();
			list.add(new int[]{nums1[tuple.i], nums2[tuple.j]});
			if (tuple.j == nums2.length - 1) {
				continue;
			}
			heap.offer(new Tuple(tuple.i, tuple.j + 1, nums1[tuple.i] + nums2[tuple.j + 1]));
		}
		
		int length = list.size();
		for (int i = 0; i < length; i++) {
			int[] array = list.get(i);
			for (int j = 0; j < array.length; j++) {
				System.out.print(array[j] + " ");
			}
			System.out.println();
		}
		return list;
	}
}
class Tuple implements Comparable<Tuple>{
	int i, j, val;
	//i and j is the row and column of the element in the matrix
	public Tuple(int i, int j, int val) {
		this.i = i;
		this.j = j;
		this.val = val;
	}
	@Override
	public int compareTo(Tuple tuple) {
		return this.val - tuple.val;
	}
	@Override
	public String toString() {
		return val + " ";
	}
}

class TuplePair implements Comparable<TuplePair>{
	int i, j, firstPair, secondPair;
	public TuplePair(int i, int j, int firstPair, int secondPair) {
		this.i = i;
		this.j = j;
		this.firstPair = firstPair;
		this.secondPair = secondPair;
	}
	
	@Override
	public int compareTo(TuplePair tuple) {
		System.out.println(this.firstPair + " " +this.secondPair + "," + tuple.firstPair + " " + tuple.secondPair);
		return (this.firstPair + this.secondPair) - (tuple.firstPair + tuple.secondPair);
	}
	
	@Override
	public String toString() {
		return "[" + firstPair + "," + secondPair + "]";
	}
}